import java.util.Arrays;
import java.util.Random;

/**
 * 双路快速排序法:解决当元素重复时时间复杂度高的问题（对于等于标定点的元素，要想办法将它分到数组的两端）
 * arr[l+1...i-1]<=v            arr[j+1...r]>=v
 */
public enum QuickSort3Ways implements Sort {
    INSTANCE;

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        Random random = new Random();
        sort(arr, 0, arr.length - 1, random);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int l, int r, Random random) {
//        if (l >= r) return;
        if (l - r <= 15) {
            insertionSort(arr, l, r);
            return;
        }
        //
        int[] partitions = partition(arr, l, r, random);
        sort(arr, l, partitions[0], random);
        sort(arr, partitions[1], r, random);
    }

    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     * @return
     * @循环不变量 arr[l+1...j] `<` v;arr[j+1...i] &gt; v
     * @优化目标：生成一个[l,r]区间的随机值，（1.生成一个[0,r-l]区间的随机值），l+[0,r-l]区间的随机值——>[l,r]区间的随机值
     */
    private <E extends Comparable<E>> int[] partition(E[] arr, int l, int r, Random random) {
        //生成[l,r]之间的随机索引
        int p = random.nextInt(r - l + 1) + l;
        SortingHelper.INSTANCE.swap(arr, l, p);

        //arr[l+1...lt]<v;arr[lt+1...i-1];arr[gt...r]>v
        int lt = l, gt = r + 1, i = l + 1;
        while (i < gt) { //
            if (arr[i].compareTo(arr[l]) < 0) {
                lt++;
                SortingHelper.INSTANCE.swap(arr, lt, i);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt--;
                SortingHelper.INSTANCE.swap(arr, gt, i);
            } else {
                i++;
            }
        }
        SortingHelper.INSTANCE.swap(arr, l, lt);
        //arr[l,lt-1]<v,arr[lt,i-1]==v,arr[gt,r]>v
        return new int[]{lt - 1, gt};

    }

    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    public <E extends Comparable<E>> void insertionSort(E[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            E t = arr[i];
            int j;
            for (j = i; j - 1 >= l && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    private <E extends Comparable<E>> void printArr(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
    }


    public static void main(String[] args) {
        int n = 100000;

        Integer[] arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        System.out.println("Random Array");
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(QuickSort3Ways.INSTANCE, arr2);
        System.out.println();

        arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, n);
        arr2 = Arrays.copyOf(arr, arr.length);

        System.out.println("Ordered Array");
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(QuickSort3Ways.INSTANCE, arr2);
        System.out.println();

        System.out.println("Same Value Array");
        arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, 1);
        arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(QuickSort3Ways.INSTANCE, arr2);
        System.out.println();
    }
}
